The present invention relates generally to error correction circuits for recording media by error correction in Reed Solomon (RS) codes and error detection in cyclic redundancy codes (CRCs) and, more particularly, to an error correction circuit with high speed CRC computation capability.
In digital audio disks (DADs), digital audio tapes (DATs), and optical disks, m bits of information are handled as a single symbol, and RS codes, in which t symbols are correctable for 2t redundancy symbols and m=8, are used.
In optical disks, RS codes for correcting 8 symbols are used in contrast to other recording media where RS codes for correcting 2 or 3 symbols are used. One way to correct 8 symbols at high speeds is to perform a repeated operation, such as Euclid or Berlekamp algorithm, with a Galois field operation circuit such as shown in Yoshida et al. "A study of Decoding RS Codes with Galois Operation Unit" The 9th Information Theory and its Application Symposium, pp. 167-170 (1986).
A conventional error correction circuit, such as shown by Yoshida et al. "Error Correction Unit for Optical Disks" Sho 61 Shin So Zen Tai, 6-53 (1987), is shown in FIG. 3. In order to handle long codes, sequence circuits for performing syndrome computation of RS codes from the received data are paralleled to find an error location.
This error correction circuit includes a buffer memory 1 for storing a plurality of interleaved data streams which includes RS codes (external codes) and CRC (internal codes); an interface 2 for untying the interleaving in the buffer memory 1; a Galois field operation circuit 3 for performing the four rules of arithmetic in the Galois field based on a syndrome of each RS code; and a sequence circuit 4 for performing not only computation of the syndrome of a RS code from each data block but also parallel operations of the Chinen search from the results of the four rules of arithmetic operation. These components are connected via data buses.
A control circuit 5 controls the interface 2, the Galois operation circuit 3, and the sequence circuit 4. A CRC coding sequence circuit, which is fabricated on a separate chip from the sequence circuit 4 and described hereinafter, is connected to the control circuit 5.
The data streams having CRCs as internal codes and RS codes as external codes are highly error detectable and has low probabilities of wrong correction in the loss correction in RS codes. The interleaved structure of these codes is highly resistant to burst errors. CRCs are a sort of cyclic codes aiming at error detection, and RS codes also are as useful for error detection as CRCs. RS codes are also used for 51/4" write-once-read many (WORM) optical disks and about to be standardized. See ISO/TC 97/SC23, Proposal for ISO, first ISO DP9171/4, July 1987.
FIG. 4 shows an exaple of the standard format of 512 bytes per sector. For the RS codes used herein, the primitive polynomial p(X) is EQU p(X)=X.sup.8 +X.sup.5 +X.sup.3 +X.sup.2 +1 (1)
and the generator polynomial G (X) is ##EQU1## wherein .alpha..sup.i =(.beta..sup.i).sup.B B and .beta. is an element of the primitive polynomial p(X). For the CRCs, the primitive plolynomial is the same as p(X) and the generator polynomial g(X) is ##EQU2## In the format of FIG. 4. an RS check symbol is provided at the end of each of code words #0-#4.
The generation of a CRC check symbol in the CRC coding sequence circuit is described below. First of all, I(X) is determined from data using the following Eq. (4). ##EQU3## wherein L is the number of interleaves, n the code length, d is the minimum distance in RS codes, and i.sub.j,k the information symbol. If i.gtoreq.L-4, then i.sub.j,o =0.
For 512 bytes per sector, L=5, n=122, d=17. Hence, the CRC check symbol C(X) with respect to I(X) is ##EQU4## wherein Re[A/B] is the excess polynomial of A/B and a (k=0-3) the CRC check symbol. The check symbol ak of Eq. (5) can be determined with a simple circuit if I(X) is given.
FIG. 5 shows such a CRC coding sequence circuit which includes an input terminal 6, an output terminal 7 for CRC check symbols a0-a4, a control signal input terminal 8 connected to the control circuit 5, four 8-bit registers 9-12, four OR circuits 13-16 each connected to the output of each register, four .alpha..sup.M multiplication circuits 17-20, wherein M is 40, 117, 228, and 97 in Eq. (3), each connected to the input of each register, and an AND gate 21 for feeding each multiplication circuit 17-20 with a logical product of an output of the OR circuit 16 and a control signal from the control signal input terminal 8.
In operation, when a reset signal is applied to the registers 9-12 via the control signal input terminal 8 to clear the contents of each register and I(X) is fed to the input terminal 6 in the order of degree, the symbol of I(X) is logically added to the output of the register 12 in the OR circuit 16 and fed to the multiplication circuits 17-20 via the AND gate 21. The data multiplied by .alpha..sup.40 in the multiplication circuit 17 is latched in the register 9 with the timing signal inputted via the control signal input terminal 8. The data multiplied by .alpha..sup.117 in the multiplication circuit 18 is logically added to the output of the register 9 in the OR circuit 13 and the result is latched in the register 10 with the timing signal inputted via the control signal input terminal 8. The data outputted from the multiplication circuits 19 and 20 are processed in the same way as above. When the entire data I(X) is inputted, the data of a0, a1, a2, and a3 of Eq. (5) are latched in the registers 9, 10, 11, and 12, respectively.
Then, after the gate 21 is turned off, these data are shifted sequentially through the registers 9-12 and the CRC check symbols a0-a3 are outputted at the output terminal 7. For coding, these CRC check symbols a0-a3 are written in the check symbol write area in the format of FIG. 4 as follows EQU a.sub.3 .fwdarw.i.sub.1,0 EQU a.sub.2 .fwdarw.i.sub.2,0 EQU a.sub.1 .fwdarw.i.sub.3,0 EQU a.sub.0 .fwdarw.i.sub.4,0
For decoding, they are compared to detect errors. The RS codes are corrected for the received words #0-#4 (data including errors) by the following steps.
(1) Find an RS code syndrome from the received word. PA1 (2) Find an error location polynomial and the error value polynomial from the syndrome. PA1 (4) Determined an error value from the error location, the error location polynomial, and the error value polynomial and make correction.
(3) Determine an error location from the error location polynomial by the Chien search.
The steps (2) and (4) are carried out by the Galois field operation circuit 3 while the steps (1) and (3) are carried out by the sequence circuit 4.
The corrected data is stored in the buffer memory 1. After all the code words (coded data) are corrected with RS codes, CRC check symbols are found in the CRC coding sequence circuit of FIG. 5, and the CRCs are computed in the OR circuit.
As described above, if I(X) is given, it is easy to determine the CRC check symbol ak, but it is necessary to not only logically add interleaved information symbols but also make the CRC check symbol portion zero at the zero order of I(X) for computation. In addition, it is impossible to start computation of CRCs in decoding until all the interleaved code words are corrected with the RS codes.